Traditional query processing engines represent a plan for performing a query with a tree of plan nodes, referred to as a query plan tree. A plan node encapsulates a single operation that is used to execute the query. The nodes are arranged as a tree in which intermediate results flow from a bottom or leaves of the tree to the top. Each node has zero or more child nodes. A child node has an output that is fed as an input to a parent node. For example, a join node will have two child nodes, which represent the two join relations, whereas a sort node would have a single child node representing the input to be sorted. The leaves of the tree are nodes which produce results by scanning stored data, for example, by performing an index scan or a sequential full table scan.
The query plan tree includes multiple nodes comprising operators implemented as an iterator. The iterator generally follows an open-next-close protocol. In a “volcano-style” query processing engine, the use of such a query plan tree may result in many virtual functions calls corresponding to the number of operators for each row being used. Extensive memory load and store may result, consuming significant resources and time to perform the query.
Another type of query processing engine generates code to perform the query with just in time compilation. Operators are fused in an execution unit referred to as a pipeline which is compiled into a single function. Code generation creates native code instead of interpreting the code. Such a fused execution unit lacks cost information and makes optimization difficult, and query processing is performed in a strictly bottom-up manner, limiting the manner of execution.